package 二叉树.练习;
//根据一棵树的前序遍历与中序遍历构造二叉树。
import 二叉树.基础.TreeNode;

public class Text_10 {
    public int preorderindex;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeChild(preorder,inorder,0,inorder.length-1);
    }
    public TreeNode buildTreeChild(int[] preorder,int[] inorder,int inBegin,int inEnd){
        if(inBegin>inEnd){
            return null;
        }

        //创建根节点
        TreeNode root = new TreeNode((char) preorder[preorderindex]);
        //获取位置
        int rootIndex = getinNow(inorder,inBegin,inEnd,preorder[preorderindex]);
        if(rootIndex==-1){
            return null;
        }
        //必须放在后面获取位置后面，不然++，还没有进行操作，缺少一位
        preorderindex++;
        root.left = buildTreeChild(preorder,inorder,inBegin,rootIndex-1);
        root.right = buildTreeChild(preorder,inorder,rootIndex+1,inEnd);


        return root;
    }

    public int  getinNow(int[] inorder,int inBegin,int inEnd,int key){
        for(int i = 0;i<=inEnd;i++){
            if(key == inorder[i]){
                return i;
            }
        }
        return -1;
    }

}